0075. 颜色分类【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 调用自带的 sort 函数
• 3. 🎯 s.2 - 冒泡排序
• 4. 🎯 s.3 - 三路快速排序方法
• 5. 🎯 s.4 - 基排序
• 6. 🫧 评价

1. 📝 题目描述

• leetcode

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

进阶：

• 你能想出一个仅使用常数空间的一趟扫描算法吗？

2. 🎯 s.1 - 调用自带的 sort 函数

/**
 * 22-08-29
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function (nums) {
  nums.sort()
}

• 虽然题目描述中明确表示不能使用库内置的 sort 函数，但实际上在开发时，这么做效率反而可能是更好的，因为内置的 sort 排序已经帮我们做了不少的优化。
• 提交记录：
  • 

3. 🎯 s.2 - 冒泡排序

/**
 * 22-08-29
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function (nums) {
  const len = nums.length
  for (let i = 0; i < len - 1; i++)
    for (let j = 0; j < len - 1 - i; j++)
      if (nums[j] > nums[j + 1]) [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]]
}

4. 🎯 s.3 - 三路快速排序方法

/**
 * 22-08-30
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function (nums) {
  const len = nums.length

  let lt = -1,
    gt = len,
    i = 0

  while (i < gt) {
    if (nums[i] < 1) {
      // 0
      lt++
      ;[nums[i], nums[lt]] = [nums[lt], nums[i]]
      i++
    } else if (nums[i] > 1) {
      // 2
      gt--
      ;[nums[i], nums[gt]] = [nums[gt], nums[i]]
    } else {
      // 1
      i++
    }
  }
}

• 设置三个 lt, gt, i 定义：nums[0...lt] == 0，nums[lt+1...i-1] = 1，nums[gt...n-1] == 2，每次遍历的时候保持这个定义。
• 

5. 🎯 s.4 - 基排序

/**
 * 22-08-30
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function (nums) {
  // 初始化一个辅助数组 arr
  const arr = [0, 0, 0]
  for (let i = 0; i < nums.length; i++) arr[nums[i]]++
  // 依据 arr 来设置 nums
  let j = 0
  for (let i = 0; i < arr.length; i++) while (arr[i]-- > 0) nums[j++] = i
}

• 思路：
  1. 用一个辅助数组 arr 记录下 nums 中的 0，1，2 的出现次数。
  2. 根据 arr 来重写 nums

6. 🫧 评价

• 本质是考察升序排序。